{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Strictly Increasing Cells in a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #array #binary-search #dynamic-programming #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数组 #二分查找 #动态规划 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxIncreasingCells"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中严格递增的单元格数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>1</strong> 开始、大小为 <code>m x n</code> 的整数矩阵 <code>mat</code>，你可以选择任一单元格作为 <strong>起始单元格</strong> 。</p>\n",
    "\n",
    "<p>从起始单元格出发，你可以移动到 <strong>同一行或同一列</strong> 中的任何其他单元格，但前提是目标单元格的值<strong> 严格大于 </strong>当前单元格的值。</p>\n",
    "\n",
    "<p>你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。</p>\n",
    "\n",
    "<p>请你找出从某个单元开始访问矩阵所能访问的 <strong>单元格的最大数量</strong> 。</p>\n",
    "\n",
    "<p>返回一个表示可访问单元格最大数量的整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/23/diag1drawio.png\" style=\"width: 200px; height: 176px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>mat = [[3,1],[3,4]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/23/diag3drawio.png\" style=\"width: 200px; height: 176px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>mat = [[1,1],[1,1]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/04/23/diag4drawio.png\" style=\"width: 350px; height: 250px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>mat = [[3,1,6],[-9,5,7]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。  \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length&nbsp;</code></li>\n",
    "\t<li><code>n == mat[i].length&nbsp;</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= mat[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-strictly-increasing-cells-in-a-matrix](https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-strictly-increasing-cells-in-a-matrix](https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,1],[3,4]]', '[[1,1],[1,1]]', '[[3,1,6],[-9,5,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict, Counter\n",
    "from heapq import heappush, heappop\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        vals = sorted((mat[i][j], i, j) for i in range(m) for j in range(n))\n",
    "        max_row = [0] * m\n",
    "        max_col = [0] * n\n",
    "        res = 0\n",
    "        left = 0\n",
    "        while left < len(vals):\n",
    "            right = left+1\n",
    "            while right < len(vals) and vals[right][0] == vals[left][0]:\n",
    "                right += 1\n",
    "            v_list = []\n",
    "            for val, i, j in vals[left:right]:\n",
    "                v = max(max_row[i], max_col[j]) + 1\n",
    "                res = max(res, v)\n",
    "                v_list.append(v)\n",
    "            for (_, i, j), v in zip(vals[left:right], v_list):\n",
    "\n",
    "                max_row[i] = max(v, max_row[i])\n",
    "                max_col[j] = max(v, max_col[j])\n",
    "            left = right\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        maxr=[0 for i in range(m)]\n",
    "        maxc=[0 for i in range(n)]\n",
    "        rcache=[0 for i in range(m)]\n",
    "        ccache=[0 for i in range(n)]\n",
    "        tls=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                tls.append([mat[i][j],i,j])\n",
    "        tls.sort(key=lambda i:i[0])\n",
    "        tlsn=len(tls)\n",
    "        logls=[]\n",
    "        for i in range(tlsn):\n",
    "            if i>0 and tls[i][0]>tls[i-1][0]:\n",
    "                for ls in logls:\n",
    "                    ccache[ls[1]]=max(ccache[ls[1]],ls[2])\n",
    "                    rcache[ls[0]]=max(rcache[ls[0]],ls[2])\n",
    "                    logls=[]\n",
    "\n",
    "            k=tls[i][1]\n",
    "            j=tls[i][2]\n",
    "            maxr[k],maxc[j] =max(rcache[k],ccache[j])+1,max(rcache[k],ccache[j])+1 \n",
    "            logls.append([k,j,maxr[k]])\n",
    "        return max(max(maxr),max(maxc))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        f = [[1]*n for _ in range(m)]\n",
    "        idx = []\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,v in enumerate(row):\n",
    "                idx.append((v,i,j))\n",
    "        r = [0]*m\n",
    "        c = [0]*n \n",
    "        idx.sort()\n",
    "        lazy = []\n",
    "        p = -10**6\n",
    "        \n",
    "        for v,i,j in idx:            \n",
    "            if v != p:\n",
    "                for a,b,x in lazy:\n",
    "                    r[a] = max(r[a],x) \n",
    "                    c[b] = max(c[b],x)\n",
    "                p = v \n",
    "                lazy = []\n",
    "            f[i][j] = max(r[i],c[j]) + 1 \n",
    "    \n",
    "            lazy.append((i,j,f[i][j]))\n",
    "        return max(max(row) for row in f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat):\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        new_data = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                new_data.append((i, j, mat[i][j]))\n",
    "        new_data.sort(key=lambda x: x[2])\n",
    "        rowmx = [-1] * n\n",
    "        colmx = [-1] * m\n",
    "        dp = [[-1] * m for _ in range(n)]\n",
    "        q = []\n",
    "        ret = 0\n",
    "        for j, (x, y, v) in enumerate(new_data):\n",
    "            if j > 0 and v > new_data[j-1][2]:\n",
    "                for (xx, yy, vv) in q:\n",
    "                    rowmx[xx] = max(rowmx[xx], vv)\n",
    "                    colmx[yy] = max(colmx[yy], vv)\n",
    "                q = []\n",
    "            dp[x][y] = max(rowmx[x], colmx[y]) + 1\n",
    "            ret = max(ret, dp[x][y])\n",
    "            q.append((x, y, dp[x][y]))\n",
    "        return ret + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        cells = sorted(((v, i, j)\n",
    "                        for i, r in enumerate(mat)\n",
    "                        for j, v in enumerate(r)), reverse=True)\n",
    "        N = len(mat)\n",
    "        M = len(mat[0])\n",
    "        row_best = [[] for _ in range(N)]\n",
    "        column_best = [[] for _ in range(M)]\n",
    "        def add_ans(v, ans, storage):\n",
    "            if not storage:\n",
    "                storage.append((v, ans))\n",
    "            elif storage[0][0] == v:\n",
    "                storage[0] = (v, max(storage[0][1], ans))\n",
    "            else:\n",
    "                storage[:] = [(v, ans), storage[0]]\n",
    "        final_ans = 0\n",
    "        for v, i, j in cells:\n",
    "            ans = max(\n",
    "                max((r[1] for r in row_best[i] if r[0] > v), default=0),\n",
    "                max((c[1] for c in column_best[j] if c[0] > v), default=0)\n",
    "            ) + 1\n",
    "            final_ans = max(final_ans, ans)\n",
    "            add_ans(v, ans, row_best[i])\n",
    "            add_ans(v, ans, column_best[j])\n",
    "        return final_ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        if mat is None:\n",
    "            return 0\n",
    "        \n",
    "        res = 0\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        infom = [None] * m\n",
    "        for i in range(m):\n",
    "            infom[i] = []\n",
    "        infon = [None] * n\n",
    "        for j in range(n):\n",
    "            infon[j] = []\n",
    "\n",
    "        info = [None] * (m * n)\n",
    "        t = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                info[t] = (mat[i][j], (i, j))\n",
    "                t += 1\n",
    "        heapq.heapify(info)\n",
    "\n",
    "        info_tmp = None\n",
    "\n",
    "        while info:\n",
    "            x, pos = heapq.heappop(info)\n",
    "            i, j = pos\n",
    "            \n",
    "\n",
    "            cnt = 1\n",
    "            info_tmp = infom[i]\n",
    "            cnti = None\n",
    "            if info_tmp and info_tmp[0][1] == mat[i][j]:\n",
    "                cnti = -info_tmp[0][0]\n",
    "                heapq.heappop(info_tmp)\n",
    "            \n",
    "            if info_tmp:\n",
    "                cnt = -info_tmp[0][0] + 1\n",
    "            \n",
    "            \n",
    "            info_tmp = infon[j]\n",
    "            cntj = None\n",
    "            if info_tmp and info_tmp[0][1] == mat[i][j]:\n",
    "                cntj = -info_tmp[0][0]\n",
    "                heapq.heappop(info_tmp)\n",
    "            \n",
    "            if info_tmp:\n",
    "                cnt = max(cnt, -info_tmp[0][0] + 1)\n",
    "            \n",
    "            if cnti is not None:\n",
    "                heapq.heappush(infom[i], (min(-cnt, -cnti), mat[i][j]))\n",
    "            else:\n",
    "                heapq.heappush(infom[i], (-cnt, mat[i][j]))\n",
    "            \n",
    "            if cntj is not None:\n",
    "                heapq.heappush(infon[j], (min(-cnt, -cntj), mat[i][j]))\n",
    "            else:\n",
    "                heapq.heappush(infon[j], (-cnt, mat[i][j]))\n",
    "            \n",
    "            res = max(res, cnt)\n",
    "\n",
    "        return res\n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        d = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[mat[i][j]].append((i, j))\n",
    "        \n",
    "        row = [0] * m\n",
    "        col = [0] * n\n",
    "\n",
    "        for num in sorted(d.keys()):\n",
    "            arr = d[num]\n",
    "            mx = [max(row[i], col[j]) + 1 for i, j in arr]\n",
    "            for (i, j), f in zip(arr, mx):\n",
    "                row[i] = max(row[i], f)\n",
    "                col[j] = max(col[j], f)\n",
    "\n",
    "        return max(max(row), max(col))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        d = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[mat[i][j]].append((i, j))\n",
    "        \n",
    "        ans = 0\n",
    "        row = [0] * m\n",
    "        col = [0] * n\n",
    "\n",
    "        for num in sorted(d.keys()):\n",
    "            arr = d[num]\n",
    "            cur_mx = 0\n",
    "            c_row = defaultdict(int)\n",
    "            c_col = defaultdict(int)\n",
    "            for i, j in arr:\n",
    "                c_row[i] = max(c_row[i], max(row[i], col[j]) + 1)\n",
    "                c_col[j] = max(c_col[j], max(row[i], col[j]) + 1)\n",
    "                cur_mx = max(cur_mx, c_row[i], c_col[j])\n",
    "            ans = max(ans, cur_mx)\n",
    "            for i, j in arr:\n",
    "                row[i] = max(row[i], c_row[i])\n",
    "                col[j] = max(col[j], c_col[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        d = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[mat[i][j]].append((i, j))\n",
    "        dp_row = [0] * m\n",
    "        dp_col = [0] * n\n",
    "        for num in sorted(d.keys(), reverse=True):\n",
    "            tmp = []\n",
    "            for x, y in d[num]:\n",
    "                tmp.append(max(dp_row[x], dp_col[y])+1)\n",
    "            for i in range(len(tmp)):\n",
    "                x, y = d[num][i]\n",
    "                dp_row[x] = max(dp_row[x], tmp[i])\n",
    "                dp_col[y] = max(dp_col[y], tmp[i])\n",
    "        return max(max(dp_row), max(dp_col))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\r\n",
    "        m = len(mat)\r\n",
    "        n = len(mat[0])\r\n",
    "        nums: dict[int, list[tuple[int, int]]] = dict()\r\n",
    "        row = [0] * m\r\n",
    "        col = [0] * n\r\n",
    "        res = 0\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                nums.setdefault(mat[i][j], list())\r\n",
    "                nums[mat[i][j]].append((i, j))\r\n",
    "        \r\n",
    "        for num in sorted(nums.keys()):\r\n",
    "            r: dict[int, int] = dict()\r\n",
    "            c: dict[int, int] = dict()\r\n",
    "            for i, j in nums[num]:\r\n",
    "                dp = max(row[i], col[j]) + 1\r\n",
    "                res = max(res, dp)\r\n",
    "                r.setdefault(i, 0)\r\n",
    "                c.setdefault(j, 0)\r\n",
    "                r[i] = max(r[i], dp)\r\n",
    "                c[j] = max(c[j], dp)\r\n",
    "            for i, cur in r.items():\r\n",
    "                row[i] = max(row[i], cur)\r\n",
    "            for j, cur in c.items():\r\n",
    "                col[j] = max(col[j], cur)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dic[mat[i][j]].append([i, j])\n",
    "        rows = [0] * m \n",
    "        cols = [0] * n \n",
    "        for val in sorted(dic.keys()):\n",
    "            nr, nc = [], []\n",
    "            for i, j in dic[val]:\n",
    "                curMax = max(rows[i], cols[j]) + 1\n",
    "                nr.append([i, curMax])\n",
    "                nc.append([j, curMax])\n",
    "            for i, c in nr:\n",
    "                rows[i] = max(rows[i], c)\n",
    "            for j, c in nc:\n",
    "                cols[j] = max(cols[j], c)\n",
    "        return max(max(rows), max(cols))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        n=len(mat)\n",
    "        m=len(mat[0])\n",
    "        dd=defaultdict(list)\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                dd[x].append((i,j))\n",
    "\n",
    "        row_max=[0]*n\n",
    "        col_max=[0]*m\n",
    "        for _,pos in sorted(dd.items()):\n",
    "            max_val=[max(row_max[i],col_max[j])+1 for i,j in pos]\n",
    "            for (i,j),f in zip(pos,max_val):\n",
    "                row_max[i]=max(row_max[i],f)\n",
    "                col_max[j]=max(col_max[j],f)\n",
    "        return max(row_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                g[x].append((i, j)) # 相同元素放在同一组，统计位置\n",
    "\n",
    "        row_max = [0] * len(mat) # 从i开始的最长递增路径\n",
    "        col_max = [0] * len(mat[0])\n",
    "        for _, pos in sorted(g.items(), key = lambda p: p[0]):\n",
    "            # 先算出最大值，再更新row_max 和 col_max\n",
    "            mx = [max(row_max[i], col_max[j]) + 1 for i, j in pos]\n",
    "            for (i, j), f in zip(pos, mx):\n",
    "                row_max[i] = max(row_max[i], f) # 更新第i行的最大f值\n",
    "                col_max[j] = max(col_max[j], f) # 更新第j列的最大f值\n",
    "        return max(row_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                g[x].append((i, j))  # 相同元素放在同一组，统计位置\n",
    "\n",
    "        row_max = [0] * len(mat)\n",
    "        col_max = [0] * len(mat[0])\n",
    "        for _, pos in sorted(g.items(), key=lambda p: p[0]):\n",
    "            # 先把最大值算出来，再更新 row_max 和 col_max\n",
    "            mx = [max(row_max[i], col_max[j]) + 1 for i, j in pos]\n",
    "            for (i, j), f in zip(pos, mx):\n",
    "                row_max[i] = max(row_max[i], f)  # 更新第 i 行的最大 f 值\n",
    "                col_max[j] = max(col_max[j], f)  # 更新第 j 列的最大 f 值\n",
    "        return max(row_max)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                g[x].append((i, j))  # 相同元素放在同一组，统计位置\n",
    "\n",
    "        row_max = [0] * len(mat)\n",
    "        col_max = [0] * len(mat[0])\n",
    "        for _, pos in sorted(g.items(), key=lambda p: p[0]):\n",
    "            # 先把最大值算出来，再更新 row_max 和 col_max\n",
    "            mx = [max(row_max[i], col_max[j]) + 1 for i, j in pos]\n",
    "            for (i, j), f in zip(pos, mx):\n",
    "                row_max[i] = max(row_max[i], f)  # 更新第 i 行的最大 f 值\n",
    "                col_max[j] = max(col_max[j], f)  # 更新第 j 列的最大 f 值\n",
    "        return max(row_max)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        n,m = len(mat), len(mat[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                graph[mat[i][j]].append((i,j))\n",
    "        \n",
    "        row_max = [0]*n\n",
    "        col_max = [0]*m\n",
    "        \n",
    "        for _, pos in sorted(graph.items(), key= lambda x:x[0]):\n",
    "            mx = [max(row_max[i], col_max[j])+1 for i,j in pos]\n",
    "            for (i,j),f in zip(pos,mx):\n",
    "                row_max[i] = max(row_max[i],f)\n",
    "                col_max[j] = max(col_max[j], f)\n",
    "        \n",
    "        return max(row_max)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        # dp[i][j] #cells transitioned to cell mat[i][j]\n",
    "        # transition increasingly from this row or col\n",
    "        # maintain max_row, max_col to keep record of max #cells transitioned\n",
    "        # calculate transition based on value asc\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row_max = [0] * m\n",
    "        col_max = [0] * n\n",
    "        cells = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                cells[mat[i][j]].append((i, j))\n",
    "\n",
    "        res = 0\n",
    "        for _, idx_list in sorted(cells.items(), key = lambda x: x[0]):    # sorted O(log(mn))\n",
    "            # take max steps from this row or col\n",
    "            mx_steps = [max(row_max[i], col_max[j]) + 1 for i, j in idx_list]\n",
    "            # update row and col max for correspondingly\n",
    "            for step, (i, j) in zip(mx_steps, idx_list):\n",
    "                row_max[i] = max(step, row_max[i])\n",
    "                col_max[j] = max(step, col_max[j])\n",
    "                res = max(res, step)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                g[x].append((i, j))  # 相同元素放在同一组，统计位置\n",
    "\n",
    "        row_max = [0] * len(mat)\n",
    "        col_max = [0] * len(mat[0])\n",
    "        for _, pos in sorted(g.items(), key=lambda p: p[0]):\n",
    "            # 先把最大值算出来，再更新 row_max 和 col_max\n",
    "            mx = [max(row_max[i], col_max[j]) + 1 for i, j in pos]\n",
    "            for (i, j), f in zip(pos, mx):\n",
    "                row_max[i] = max(row_max[i], f)  # 更新第 i 行的最大 f 值\n",
    "                col_max[j] = max(col_max[j], f)  # 更新第 j 列的最大 f 值\n",
    "        return max(row_max)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 从大到小\n",
    "# class Solution:\n",
    "#     def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "#         m = len(mat)\n",
    "#         n = len(mat[0])\n",
    "#         tup = []\n",
    "#         counter = {}       \n",
    "#         for r in range(m):\n",
    "#             for c in range(n):\n",
    "#                 d = mat[r][c]\n",
    "#                 tup.append([d, r, c])\n",
    "#                 if d in counter:\n",
    "#                     counter[d].append((r, c))\n",
    "#                 else:\n",
    "#                     counter[d] = [(r, c)]        \n",
    "#         tup.sort()\n",
    "#         rowMax = [0] * m\n",
    "#         colMax = [0] * n\n",
    "#         ans = 1\n",
    "#         dp = [[0] * n for _ in range(m)]        \n",
    "#         for i in range(len(tup) - 1, -1, -1):\n",
    "#             r = tup[i][1]\n",
    "#             c = tup[i][2]\n",
    "#             dp[r][c] = max(rowMax[r], colMax[c]) + 1            \n",
    "#             if i == 0 or tup[i - 1][0] != tup[i][0]:\n",
    "#                 for pir in counter[mat[r][c]]:\n",
    "#                     rowMax[pir[0]] = max(rowMax[pir[0]], dp[pir[0]][pir[1]])\n",
    "#                     colMax[pir[1]] = max(colMax[pir[1]], dp[pir[0]][pir[1]])           \n",
    "#             ans = max(ans, dp[r][c])      \n",
    "#         return ans\n",
    "\n",
    "# # 从小到大枚举mat[r][c]，dp[r][c]表示到mat[r][c]为止，最多可以访问的cells。用rowMaxDp[r]记录r行最大的dp，用columnMaxDp[c]记录c列最大的dp\n",
    "# # 每次出现一个新的数，因为它是当前最大数，所以dp[r][c] = max(rowMaxDp[r], columnMaxDp[c]) + 1\n",
    "# # 当有一组相同的数时，要一次把这一组计算完成后，才能更新dp、rowMaxDp、columnMaxDp的值。因为相等的数之间不可达，中途更新将导致错误的结果。\n",
    "# 最后答案是所有dp中最大的一个\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        row = len(mat)\n",
    "        column = len(mat[0])\n",
    "        maxCells = 0\n",
    "        numIndices = defaultdict(list)\n",
    "        rowMaxDp = [0] * row\n",
    "        columnMaxDp = [0] * column\n",
    "        for r in range(row):\n",
    "            for c in range(column):\n",
    "            #把相等的数分在同一组。因为相等的数之间不可达，所以要一次计算完所有相等的数。\n",
    "                numIndices[mat[r][c]].append((r, c))    \n",
    "        \n",
    "        for num, indices in sorted(numIndices.items()):\n",
    "            size = len(indices)\n",
    "            dps = [float('-inf')] * size    #  计算这一组数的dp\n",
    "            for i in range(size):\n",
    "                r, c = indices[i]\n",
    "                dps[i] = max(rowMaxDp[r], columnMaxDp[c]) + 1   # 从比它小的数都可以到达mat[r][c]，所以选最大的一个，然后加上mat[r][c]自己\n",
    "                maxCells = max(maxCells, dps[i])    # 最终答案是所有dp中最大的一个\n",
    "            for i in range(size):\n",
    "                r, c = indices[i]\n",
    "                rowMaxDp[r] = max(rowMaxDp[r], dps[i])  #这一组计算完成后，才能更新rowMaxDp、columnMaxDp的值。因为相等的数不可达，中途更新将导致错误的结果。\n",
    "                columnMaxDp[c] = max(columnMaxDp[c], dps[i])\n",
    "        return maxCells\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 从大到小\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        tup = []\n",
    "        counter = {}       \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                d = mat[r][c]\n",
    "                tup.append([d, r, c])\n",
    "                if d in counter:\n",
    "                    counter[d].append((r, c))\n",
    "                else:\n",
    "                    counter[d] = [(r, c)]        \n",
    "        tup.sort()\n",
    "        rowMax = [0] * m\n",
    "        colMax = [0] * n\n",
    "        ans = 1\n",
    "        dp = [[0] * n for _ in range(m)]        \n",
    "        for i in range(len(tup) - 1, -1, -1):\n",
    "            r = tup[i][1]\n",
    "            c = tup[i][2]\n",
    "            dp[r][c] = max(rowMax[r], colMax[c]) + 1            \n",
    "            if i == 0 or tup[i - 1][0] != tup[i][0]:\n",
    "                for pir in counter[mat[r][c]]:\n",
    "                    rowMax[pir[0]] = max(rowMax[pir[0]], dp[pir[0]][pir[1]])\n",
    "                    colMax[pir[1]] = max(colMax[pir[1]], dp[pir[0]][pir[1]])           \n",
    "            ans = max(ans, dp[r][c])      \n",
    "        return ans\n",
    "\n",
    "\n",
    "# 从小到大\n",
    "# # 从小到大枚举mat[r][c]，dp[r][c]表示到mat[r][c]为止，最多可以访问的cells。用rowMaxDp[r]记录r行最大的dp，用columnMaxDp[c]记录c列最大的dp\n",
    "# # 每次出现一个新的数，因为它是当前最大数，所以dp[r][c] = max(rowMaxDp[r], columnMaxDp[c]) + 1\n",
    "# # 当有一组相同的数时，要一次把这一组计算完成后，才能更新dp、rowMaxDp、columnMaxDp的值。因为相等的数之间不可达，中途更新将导致错误的结果。\n",
    "# 最后答案是所有dp中最大的一个\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        row = len(mat)\n",
    "        column = len(mat[0])\n",
    "        maxCells = 0\n",
    "        numIndices = defaultdict(list)\n",
    "        rowMaxDp = [0] * row\n",
    "        columnMaxDp = [0] * column\n",
    "        for r in range(row):\n",
    "            for c in range(column):\n",
    "            #把相等的数分在同一组。因为相等的数之间不可达，所以要一次计算完所有相等的数。\n",
    "                numIndices[mat[r][c]].append((r, c))            \n",
    "        for num, indices in sorted(numIndices.items()):\n",
    "            size = len(indices)\n",
    "            dps = [float('-inf')] * size    #  计算这一组数的dp\n",
    "            for i in range(size):\n",
    "                r, c = indices[i]\n",
    "                dps[i] = max(rowMaxDp[r], columnMaxDp[c]) + 1   # 从比它小的数都可以到达mat[r][c]，所以选最大的一个，然后加上mat[r][c]自己\n",
    "                maxCells = max(maxCells, dps[i])    # 最终答案是所有dp中最大的一个\n",
    "            for i in range(size):\n",
    "                r, c = indices[i]\n",
    "                rowMaxDp[r] = max(rowMaxDp[r], dps[i])  #这一组计算完成后，才能更新rowMaxDp、columnMaxDp的值。因为相等的数不可达，中途更新将导致错误的结果。\n",
    "                columnMaxDp[c] = max(columnMaxDp[c], dps[i])\n",
    "        return maxCells\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                g[x].append((i, j))  # 相同元素放在同一组，统计位置\n",
    "        row_max = [0] * len(mat)\n",
    "        col_max = [0] * len(mat[0])\n",
    "        # 代码实现时 f[i][j]可以省略，因为只需要每行每列的f值的最大值。\n",
    "        for _, pos in sorted(g.items(), key=lambda p: p[0]):\n",
    "            # 先把最大值算出来，再更新 row_max 和 col_max\n",
    "            mx = [max(row_max[i], col_max[j]) + 1 for i, j in pos]\n",
    "            for (i, j), f in zip(pos, mx):\n",
    "                row_max[i] = max(row_max[i], f)  # 更新第 i 行的最大 f 值\n",
    "                col_max[j] = max(col_max[j], f)  # 更新第 j 列的最大 f 值\n",
    "        return max(row_max)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/python\n",
    "# -*- encoding: utf-8 -*-\n",
    "'''\n",
    "@File    :   2713.矩阵中严格递增的单元格数.py\n",
    "@Time    :   2023/09/30 03:09:36\n",
    "@Author  :   Yuan\n",
    "'''\n",
    "\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedDict, SortedList\n",
    "from functools import cache, lru_cache\n",
    "from collections import deque, Counter, OrderedDict \n",
    "from bisect import bisect_left, bisect_right\n",
    "import math\n",
    "from math import inf\n",
    "import heapq\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "#         m, n = len(mat), len(mat[0])\n",
    "#         @cache\n",
    "#         def f(i, j):\n",
    "#             s = 1\n",
    "#             for x in range(m):\n",
    "#                 if mat[x][j] > mat[i][j]:\n",
    "#                     s = max(s, f(x, j) + 1)\n",
    "\n",
    "#             for y in range(n):\n",
    "#                 if mat[i][y] > mat[i][j]:\n",
    "#                     s = max(s, f(i, y) + 1)\n",
    "\n",
    "#             return s \n",
    "\n",
    "#         ans = -inf\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 ans = max(ans, f(i, j))\n",
    "#         return ans \n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row = [0] * m \n",
    "        col = [0] * n\n",
    "\n",
    "        S = SortedDict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i][j] not in S:\n",
    "                    S[mat[i][j]] = []\n",
    "                \n",
    "                S[mat[i][j]].append((i, j))\n",
    "\n",
    "\n",
    "        for _, pos in sorted(S.items(), key=lambda p: p[0]): \n",
    "            update = []\n",
    "            for x, y in pos:\n",
    "                tmpx = row[x] + 1\n",
    "                tmpy = col[y] + 1\n",
    "                t = max(tmpx, tmpy)\n",
    "                update.append((t, x, y))\n",
    "            for t, x, y in update:\n",
    "                row[x] = max(row[x], t)\n",
    "                col[y] = max(col[y], t)\n",
    "           \n",
    "        return max(row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        val_2_idxes = collections.defaultdict(list)\n",
    "        rows_max, cols_max = [0] * m, [0] * n\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                val_2_idxes[mat[i][j]].append([i, j])\n",
    "        \n",
    "        for _, indexes in sorted(val_2_idxes.items()):  # sort by value\n",
    "            # transition from same row or column\n",
    "            steps = [max(rows_max[i], cols_max[j]) + 1 for i, j in indexes]\n",
    "\n",
    "            for (i, j), step in zip(indexes, steps):\n",
    "                rows_max[i] = max(step, rows_max[i])\n",
    "                cols_max[j] = max(step, cols_max[j])\n",
    "                res = max(res, step)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        val_2_idxes = collections.defaultdict(list)\n",
    "        rows_max, cols_max = [0] * m, [0] * n\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                val_2_idxes[mat[i][j]].append([i, j])\n",
    "        \n",
    "        for _, indexes in sorted(val_2_idxes.items()):  # sort by value\n",
    "            # transition from same row or column\n",
    "            # only indexes for this val are updated\n",
    "            steps = [max(rows_max[i], cols_max[j]) + 1 for i, j in indexes]\n",
    "\n",
    "            for (i, j), step in zip(indexes, steps):\n",
    "                rows_max[i] = max(step, rows_max[i])\n",
    "                cols_max[j] = max(step, cols_max[j])\n",
    "                res = max(res, step)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        val_2_indexes = defaultdict(list)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                val_2_indexes[mat[i][j]].append([i, j])\n",
    "\n",
    "        row_trans = [0] * m\n",
    "        col_trans = [0] * n\n",
    "        res = 0\n",
    "        for _, indexes in sorted(val_2_indexes.items()):\n",
    "            steps = [max(row_trans[i], col_trans[j]) + 1 for i, j in indexes]\n",
    "            \n",
    "            for step, (i, j) in zip(steps, indexes):\n",
    "                row_trans[i] = max(step, row_trans[i])\n",
    "                col_trans[j] = max(step, col_trans[j])\n",
    "                res = max(res, step)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(list)\n",
    "        m,n = len(mat), len(mat[0])\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                d[mat[x][y]].append((x,y))\n",
    "        ans = 0\n",
    "        rowmax = [0] * m\n",
    "        colmax = [0] * n\n",
    "        for _,pos in sorted(d.items(), key=lambda x:x[0]):\n",
    "            remember = [max(rowmax[x], colmax[y])+1 for (x,y) in pos]\n",
    "            ans = max(ans ,max(remember))\n",
    "            # 最后更新rowmax 和 colmax\n",
    "            for f, (i,j) in zip(remember, pos):\n",
    "                rowmax[i] = max(f, rowmax[i])\n",
    "                colmax[j] = max(f, colmax[j])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        g=defaultdict(list) \n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                g[x].append((i,j))\n",
    "\n",
    "        ans=0\n",
    "        row_max=[0]*len(mat)\n",
    "        col_max=[0]*len(mat[0])\n",
    "        for _,pos in sorted(g.items(),key=lambda p:p[0]):\n",
    "            mx=[max(row_max[i],col_max[j])+1 for i,j in pos]\n",
    "            ans=max(ans,max(mx))\n",
    "            for (i,j),f in zip(pos,mx):\n",
    "                row_max[i]=max(row_max[i],f)\n",
    "                col_max[j]=max(col_max[j],f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        grp = defaultdict(list)\n",
    "        M, N = len(mat), len(mat[0])\n",
    "        \n",
    "        for i, j in itertools.product(range(M), range(N)):\n",
    "            grp[mat[i][j]].append((i, j))\n",
    "\n",
    "        row, col = [0] * M, [0] * N\n",
    "        res = 0\n",
    "        for _, pos in sorted(grp.items(), key=lambda x:x[0]):\n",
    "            mx = [max(row[i], col[j]) + 1 for i, j in pos]\n",
    "            res = max(res, *mx)\n",
    "            \n",
    "            for (i, j), v in zip(pos, mx):\n",
    "                row[i] = max(row[i], v)\n",
    "                col[j] = max(col[j], v)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, val in enumerate(row):\n",
    "                g[val].append((i, j))\n",
    "\n",
    "        ans = 0\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        max_row = [0] * m\n",
    "        max_col = [0] * n\n",
    "        for _, pos in sorted(g.items(), key=lambda x: x[0]):\n",
    "            mx = [max(max_row[i], max_col[j]) + 1 for i, j in pos]\n",
    "            ans = max(ans, max(mx))\n",
    "            for (i, j), f in zip(pos, mx):\n",
    "                max_row[i] = max(max_row[i], f)\n",
    "                max_col[j] = max(max_col[j], f)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos[mat[i][j]].append((i, j))\n",
    "        row_max_f = [0 for i in range(m)]\n",
    "        col_max_f = [0 for j in range(n)]\n",
    "        for _, poses in sorted(pos.items(), key=lambda p: p[0]):\n",
    "            fs = [max(row_max_f[i], col_max_f[j]) + 1 for i, j in poses]\n",
    "            for f, (i, j) in zip(fs, poses):\n",
    "                row_max_f[i] = max(row_max_f[i], f)\n",
    "                col_max_f[j] = max(col_max_f[j], f)\n",
    "        return max(row_max_f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 从大到小\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        tup = []\n",
    "        counter = {}       \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                d = mat[r][c]\n",
    "                tup.append([d, r, c])\n",
    "                if d in counter:\n",
    "                    counter[d].append((r, c))\n",
    "                else:\n",
    "                    counter[d] = [(r, c)]        \n",
    "        tup.sort()\n",
    "        rowMax = [0] * m\n",
    "        colMax = [0] * n\n",
    "        ans = 1\n",
    "        dp = [[0] * n for _ in range(m)]        \n",
    "        for i in range(len(tup) - 1, -1, -1):\n",
    "            r = tup[i][1]\n",
    "            c = tup[i][2]\n",
    "            dp[r][c] = max(rowMax[r], colMax[c]) + 1            \n",
    "            if i == 0 or tup[i - 1][0] != tup[i][0]:\n",
    "                for pir in counter[mat[r][c]]:\n",
    "                    rowMax[pir[0]] = max(rowMax[pir[0]], dp[pir[0]][pir[1]])\n",
    "                    colMax[pir[1]] = max(colMax[pir[1]], dp[pir[0]][pir[1]])           \n",
    "            ans = max(ans, dp[r][c])      \n",
    "        return ans\n",
    "\n",
    "# # 从小到大枚举mat[r][c]，dp[r][c]表示到mat[r][c]为止，最多可以访问的cells。用rowMaxDp[r]记录r行最大的dp，用columnMaxDp[c]记录c列最大的dp\n",
    "# # 每次出现一个新的数，因为它是当前最大数，所以dp[r][c] = max(rowMaxDp[r], columnMaxDp[c]) + 1\n",
    "# # 当有一组相同的数时，要一次把这一组计算完成后，才能更新dp、rowMaxDp、columnMaxDp的值。因为相等的数之间不可达，中途更新将导致错误的结果。\n",
    "# 最后答案是所有dp中最大的一个\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        row = len(mat)\n",
    "        column = len(mat[0])\n",
    "        maxCells = 0\n",
    "        numIndices = defaultdict(list)\n",
    "        rowMaxDp = [0] * row\n",
    "        columnMaxDp = [0] * column\n",
    "        for r in range(row):\n",
    "            for c in range(column):\n",
    "            #把相等的数分在同一组。因为相等的数之间不可达，所以要一次计算完所有相等的数。\n",
    "                numIndices[mat[r][c]].append((r, c))    \n",
    "        \n",
    "        for num, indices in sorted(numIndices.items()):\n",
    "            size = len(indices)\n",
    "            dps = [float('-inf')] * size    #  计算这一组数的dp\n",
    "            for i in range(size):\n",
    "                r, c = indices[i]\n",
    "                dps[i] = max(rowMaxDp[r], columnMaxDp[c]) + 1   # 从比它小的数都可以到达mat[r][c]，所以选最大的一个，然后加上mat[r][c]自己\n",
    "                maxCells = max(maxCells, dps[i])    # 最终答案是所有dp中最大的一个\n",
    "            for i in range(size):\n",
    "                r, c = indices[i]\n",
    "                rowMaxDp[r] = max(rowMaxDp[r], dps[i])  #这一组计算完成后，才能更新rowMaxDp、columnMaxDp的值。因为相等的数不可达，中途更新将导致错误的结果。\n",
    "                columnMaxDp[c] = max(columnMaxDp[c], dps[i])\n",
    "        return maxCells\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        res = []\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        cache = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = mat[i][j]\n",
    "                cache[x].append((i,j))\n",
    "        rowMax = [0] * m\n",
    "        colMax = [0] * n\n",
    "        nums = [key for key in cache]\n",
    "        nums.sort()\n",
    "        f = [[0] * n for i in range(m)]\n",
    "        for key in nums:\n",
    "            for i,j in cache[key]:\n",
    "                f[i][j] = max(rowMax[i], colMax[j]) + 1\n",
    "            for i,j in cache[key]:\n",
    "                rowMax[i] = max(f[i][j], rowMax[i])\n",
    "                colMax[j] = max(f[i][j], colMax[j])\n",
    "        return max(item  for row in f for item in row)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 从大到小\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        tup = []\n",
    "        counter = {}       \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                d = mat[r][c]\n",
    "                tup.append([d, r, c])\n",
    "                if d in counter:\n",
    "                    counter[d].append((r, c))\n",
    "                else:\n",
    "                    counter[d] = [(r, c)]        \n",
    "        tup.sort()\n",
    "        rowMax = [0] * m\n",
    "        colMax = [0] * n\n",
    "        ans = 1\n",
    "        dp = [[0] * n for _ in range(m)]        \n",
    "        for i in range(len(tup) - 1, -1, -1):\n",
    "            r = tup[i][1]\n",
    "            c = tup[i][2]\n",
    "            dp[r][c] = max(rowMax[r], colMax[c]) + 1            \n",
    "            if i == 0 or tup[i - 1][0] != tup[i][0]:\n",
    "                for pir in counter[mat[r][c]]:\n",
    "                    rowMax[pir[0]] = max(rowMax[pir[0]], dp[pir[0]][pir[1]])\n",
    "                    colMax[pir[1]] = max(colMax[pir[1]], dp[pir[0]][pir[1]])           \n",
    "            ans = max(ans, dp[r][c])      \n",
    "        return ans\n",
    "\n",
    "# # 从小到大枚举mat[r][c]，dp[r][c]表示到mat[r][c]为止，最多可以访问的cells。用rowMaxDp[r]记录r行最大的dp，用columnMaxDp[c]记录c列最大的dp\n",
    "# # 每次出现一个新的数，因为它是当前最大数，所以dp[r][c] = max(rowMaxDp[r], columnMaxDp[c]) + 1\n",
    "# # 当有一组相同的数时，要一次把这一组计算完成后，才能更新dp、rowMaxDp、columnMaxDp的值。因为相等的数之间不可达，中途更新将导致错误的结果。\n",
    "# # 最后答案是所有dp中最大的一个\n",
    "# from collections import defaultdict\n",
    "# class Solution:\n",
    "#     def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "#         row = len(mat)\n",
    "#         column = len(mat[0])\n",
    "#         maxCells = 0\n",
    "#         numIndices = defaultdict(list)\n",
    "#         rowMaxDp = [0] * row\n",
    "#         columnMaxDp = [0] * column\n",
    "#         for r in range(row):\n",
    "#             for c in range(column):\n",
    "#             #把相等的数分在同一组。因为相等的数之间不可达，所以要一次计算完所有相等的数。\n",
    "#                 numIndices[mat[r][c]].append((r, c))    \n",
    "#         for num, indices in numIndices.items():\n",
    "#             size = len(indices)\n",
    "#             dps = [float('-inf')] * size    #  计算这一组数的dp\n",
    "#             for i in range(size):\n",
    "#                 r, c = indices[i]\n",
    "#                 dps[i] = max(rowMaxDp[r], columnMaxDp[c]) + 1   # 从比它小的数都可以到达mat[r][c]，所以选最大的一个，然后加上mat[r][c]自己\n",
    "#                 maxCells = max(maxCells, dps[i])    # 最终答案是所有dp中最大的一个\n",
    "#             for i in range(size):\n",
    "#                 r, c = indices[i]\n",
    "#                 rowMaxDp[r] = max(rowMaxDp[r], dps[i])  #这一组计算完成后，才能更新rowMaxDp、columnMaxDp的值。因为相等的数不可达，中途更新将导致错误的结果。\n",
    "#                 columnMaxDp[c] = max(columnMaxDp[c], dps[i])\n",
    "#         return maxCells\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        # def lt2713(mat):\n",
    "        #     m,n=len(mat),len(mat[0])\n",
    "        #     record=[[None for j in range(n)] for i in range(m)]\n",
    "        #     def dfs(i,j):\n",
    "        #         if not record[i][j]:\n",
    "        #             temp=[1]\n",
    "        #             for u in range(m):\n",
    "        #                 if u!=i and mat[u][j]<mat[i][j]:temp.append(dfs(u,j)+1)\n",
    "        #             for v in range(n):\n",
    "        #                 if v!=j and mat[i][v]<mat[i][j]:temp.append(dfs(i,v)+1)\n",
    "        #             record[i][j]=max(temp)\n",
    "        #         return record[i][j]\n",
    "        #     max_=1\n",
    "        #     for i in range(m):\n",
    "        #         for j in range(n):\n",
    "        #             max_=max(max_,dfs(i,j))\n",
    "        #     return max_\n",
    "        # return lt2713(mat)\n",
    "\n",
    "        # def lt2713(mat):\n",
    "        #     m,n=len(mat),len(mat[0])\n",
    "        #     record=[[None for j in range(n)] for i in range(m)]\n",
    "        #     rows,cols=defaultdict(list),defaultdict(list)\n",
    "        #     for i in range(m):\n",
    "        #         temp=[(i,j) for j in range(n)]\n",
    "        #         temp.sort(key=lambda x:mat[x[0]][x[1]])\n",
    "        #         for k in range(n):\n",
    "        #             for _ in range(k-1,-1,-1):\n",
    "        #                 if mat[temp[_][0]][temp[_][1]]<mat[temp[k][0]][temp[k][1]]:\n",
    "        #                     rows[temp[k]]=temp[:_+1]\n",
    "        #                     break\n",
    "        #     for j in range(n):\n",
    "        #         temp=[(i,j) for i in range(m)]\n",
    "        #         temp.sort(key=lambda x:mat[x[0]][x[1]])\n",
    "        #         for k in range(m):\n",
    "        #             for _ in range(k-1,-1,-1):\n",
    "        #                 if mat[temp[_][0]][temp[_][1]]<mat[temp[k][0]][temp[k][1]]:\n",
    "        #                     cols[temp[k]]=temp[:_+1]\n",
    "        #                     break\n",
    "\n",
    "        #     def dfs(i,j):\n",
    "        #         if not record[i][j]:\n",
    "        #             temp=[1]\n",
    "        #             for u,v in rows[(i,j)]:temp.append(dfs(u,v)+1)\n",
    "        #             for u,v in cols[(i,j)]:temp.append(dfs(u,v)+1)\n",
    "        #             record[i][j]=max(temp)\n",
    "        #         return record[i][j]\n",
    "        #     max_=1\n",
    "        #     for i in range(m):\n",
    "        #         for j in range(n):\n",
    "        #             max_=max(max_,dfs(i,j))\n",
    "        #     return max_\n",
    "        # return lt2713(mat)\n",
    "\n",
    "        def lt2713(mat):\n",
    "            m,n=len(mat),len(mat[0])\n",
    "            record=[[None for j in range(n)] for i in range(m)]\n",
    "            rows,cols=defaultdict(list),defaultdict(list)\n",
    "            for i in range(m):\n",
    "                temp=[(i,j) for j in range(n)]\n",
    "                temp.sort(key=lambda x:mat[x[0]][x[1]])\n",
    "                for k in range(n):\n",
    "                    flag=None\n",
    "                    for _ in range(k-1,-1,-1):\n",
    "                        if not flag:\n",
    "                            if mat[temp[_][0]][temp[_][1]]<mat[temp[k][0]][temp[k][1]]:\n",
    "                                rows[temp[k]].append(temp[_])\n",
    "                                flag=mat[temp[_][0]][temp[_][1]]\n",
    "                        else:\n",
    "                            if mat[temp[_][0]][temp[_][1]]==flag:\n",
    "                                rows[temp[k]].append(temp[_])\n",
    "                            else:break\n",
    "            for j in range(n):\n",
    "                temp=[(i,j) for i in range(m)]\n",
    "                temp.sort(key=lambda x:mat[x[0]][x[1]])\n",
    "                for k in range(m):\n",
    "                    flag=None\n",
    "                    for _ in range(k-1,-1,-1):\n",
    "                        if not flag:\n",
    "                            if mat[temp[_][0]][temp[_][1]]<mat[temp[k][0]][temp[k][1]]:\n",
    "                                cols[temp[k]].append(temp[_])\n",
    "                                flag=mat[temp[_][0]][temp[_][1]]\n",
    "                        else:\n",
    "                            if mat[temp[_][0]][temp[_][1]]==flag:\n",
    "                                cols[temp[k]].append(temp[_])\n",
    "                            else:break\n",
    "            def dfs(i,j):\n",
    "                if not record[i][j]:\n",
    "                    temp=[1]\n",
    "                    for u,v in rows[(i,j)]:temp.append(dfs(u,v)+1)\n",
    "                    for u,v in cols[(i,j)]:temp.append(dfs(u,v)+1)\n",
    "                    record[i][j]=max(temp)\n",
    "                return record[i][j]\n",
    "            max_=1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    max_=max(max_,dfs(i,j))\n",
    "            return max_\n",
    "        return lt2713(mat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        e = defaultdict(set)\n",
    "        d = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            tmp = []\n",
    "            for j in range(m):\n",
    "                tmp.append([mat[i][j],i,j])\n",
    "            tmp.sort()\n",
    "            c = defaultdict(set)\n",
    "            vv = set()\n",
    "            for v,x,y in tmp:\n",
    "                c[v].add((x,y))\n",
    "                vv.add(v)\n",
    "            vv = sorted(list(vv))\n",
    "            ll = len(vv)\n",
    "            for k in range(1,ll):\n",
    "                lst,cur = vv[k - 1],vv[k]\n",
    "                for x1,y1 in c[lst]:\n",
    "                    for x2,y2 in c[cur]:\n",
    "                        e[(x1,y1)].add((x2,y2))\n",
    "                        d[(x2,y2)] += 1\n",
    "        for j in range(m):\n",
    "            tmp = []\n",
    "            for i in range(n):\n",
    "                tmp.append([mat[i][j],i,j])\n",
    "            tmp.sort()\n",
    "            c = defaultdict(set)\n",
    "            vv = set()\n",
    "            for v,x,y in tmp:\n",
    "                c[v].add((x,y))\n",
    "                vv.add(v)\n",
    "            vv = sorted(list(vv))\n",
    "            \n",
    "            ll = len(vv)\n",
    "            for k in range(1,ll):\n",
    "                lst,cur = vv[k - 1],vv[k]\n",
    "                for x1,y1 in c[lst]:\n",
    "                    for x2,y2 in c[cur]:\n",
    "                        e[(x1,y1)].add((x2,y2))\n",
    "                        d[(x2,y2)] += 1\n",
    "        #print(e)\n",
    "        q = deque()\n",
    "        dp = [[1 for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if d[(i,j)] == 0:\n",
    "                    q.append((i,j))\n",
    "        while q:\n",
    "            x,y = q.popleft()\n",
    "            for nx,ny in e[(x,y)]:\n",
    "                dp[nx][ny] = max(dp[nx][ny],dp[x][y] + 1)\n",
    "                d[(nx,ny)] -= 1\n",
    "                if d[(nx,ny)] == 0:\n",
    "                    q.append((nx,ny))\n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans = max(ans,dp[i][j])\n",
    "        return ans\n",
    "        \n",
    "                \n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        e = defaultdict(set)\n",
    "        indeg = defaultdict(int)\n",
    "        virid = n * m\n",
    "        notcan = n * m\n",
    "        # processing every rows\n",
    "        for i in range(n):\n",
    "            cnt = defaultdict(list)\n",
    "            for j in range(m):\n",
    "                cnt[mat[i][j]].append([i,j])\n",
    "            cnt = sorted(list(cnt.items()),key = lambda x:x[0])\n",
    "            tmp = virid\n",
    "            for j in range(1,len(cnt)):\n",
    "                for x,y in cnt[j][1]:\n",
    "                    indeg[x * m + y] += 1\n",
    "                    e[virid].add(x * m + y)\n",
    "                    if j != len(cnt) - 1:\n",
    "                        indeg[virid + 1] += 1\n",
    "                        e[x * m + y].add(virid + 1)\n",
    "                virid += 1\n",
    "            if len(cnt) > 1:\n",
    "                for x,y in cnt[0][1]:\n",
    "                    indeg[tmp] += 1\n",
    "                    e[x * m + y].add(tmp)\n",
    "        \n",
    "        # processing every columns\n",
    "        for j in range(m):\n",
    "            cnt = defaultdict(list)\n",
    "            for i in range(n):\n",
    "                cnt[mat[i][j]].append([i,j])\n",
    "            cnt = sorted(list(cnt.items()),key = lambda x:x[0])\n",
    "            tmp = virid\n",
    "            for i in range(1,len(cnt)):\n",
    "                for x,y in cnt[i][1]:\n",
    "                    indeg[x * m + y] += 1\n",
    "                    e[virid].add(x * m + y)\n",
    "                    if i != len(cnt) - 1:\n",
    "                        indeg[virid + 1] += 1\n",
    "                        e[x * m + y].add(virid + 1)\n",
    "                virid += 1\n",
    "            if len(cnt) > 1:\n",
    "                for x,y in cnt[0][1]:\n",
    "                    indeg[tmp] += 1\n",
    "                    e[x * m + y].add(tmp)\n",
    "        \n",
    "        dp = defaultdict(int)\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if indeg[i * m + j] == 0:\n",
    "                    q.append(i * m + j)\n",
    "                    dp[i * m + j] = 1\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nxt in e[cur]:\n",
    "                indeg[nxt] -= 1\n",
    "                dp[nxt] = max(dp[nxt],dp[cur])\n",
    "                if indeg[nxt] == 0:\n",
    "                    if nxt < notcan:\n",
    "                        dp[nxt] += 1\n",
    "                    q.append(nxt)\n",
    "        ans = 0\n",
    "        for v in dp:\n",
    "            ans = max(ans,dp[v])\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        e = defaultdict(set)\n",
    "        indeg = defaultdict(int)\n",
    "        virid = n * m\n",
    "        notcan = n * m\n",
    "        # processing every rows\n",
    "        for i in range(n):\n",
    "            cnt = defaultdict(list)\n",
    "            for j in range(m):\n",
    "                cnt[mat[i][j]].append([i,j])\n",
    "            cnt = sorted(list(cnt.items()),key = lambda x:x[0])\n",
    "            tmp = virid\n",
    "            for j in range(1,len(cnt)):\n",
    "                for x,y in cnt[j][1]:\n",
    "                    indeg[x * m + y] += 1\n",
    "                    e[virid].add(x * m + y)\n",
    "                    if j != len(cnt) - 1:\n",
    "                        indeg[virid + 1] += 1\n",
    "                        e[x * m + y].add(virid + 1)\n",
    "                virid += 1\n",
    "            if len(cnt) > 1:\n",
    "                for x,y in cnt[0][1]:\n",
    "                    indeg[tmp] += 1\n",
    "                    e[x * m + y].add(tmp)\n",
    "        \n",
    "        # processing every columns\n",
    "        for j in range(m):\n",
    "            cnt = defaultdict(list)\n",
    "            for i in range(n):\n",
    "                cnt[mat[i][j]].append([i,j])\n",
    "            cnt = sorted(list(cnt.items()),key = lambda x:x[0])\n",
    "            tmp = virid\n",
    "            for i in range(1,len(cnt)):\n",
    "                for x,y in cnt[i][1]:\n",
    "                    indeg[x * m + y] += 1\n",
    "                    e[virid].add(x * m + y)\n",
    "                    if i != len(cnt) - 1:\n",
    "                        indeg[virid + 1] += 1\n",
    "                        e[x * m + y].add(virid + 1)\n",
    "                virid += 1\n",
    "            if len(cnt) > 1:\n",
    "                for x,y in cnt[0][1]:\n",
    "                    indeg[tmp] += 1\n",
    "                    e[x * m + y].add(tmp)\n",
    "        \n",
    "        dp = defaultdict(int)\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if indeg[i * m + j] == 0:\n",
    "                    q.append(i * m + j)\n",
    "                    dp[i * m + j] = 1\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nxt in e[cur]:\n",
    "                indeg[nxt] -= 1\n",
    "                dp[nxt] = max(dp[nxt],dp[cur])\n",
    "                if indeg[nxt] == 0:\n",
    "                    if nxt < notcan:\n",
    "                        dp[nxt] += 1\n",
    "                    q.append(nxt)\n",
    "        ans = 0\n",
    "        for v in dp:\n",
    "            ans = max(ans,dp[v])\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, g: List[List[int]]) -> int:\n",
    "        m,n=len(g),len(g[0])\n",
    "        r=[sorted([(g[i][j],i,j) for j in range(n)]) for i in range(m)]\n",
    "        c=[sorted([(g[i][j],i,j) for i in range(m)]) for j in range(n)]\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            k1=bisect_right(r[x],(g[x][y],inf,inf))\n",
    "            ans=1\n",
    "            k=k1\n",
    "            while k<n and r[x][k][0]==r[x][k1][0]:\n",
    "                v,nx,ny=r[x][k]\n",
    "                ans=max(ans,dfs(nx,ny)+1)\n",
    "                k+=1\n",
    "            k2=bisect_right(c[y],(g[x][y],inf,inf))\n",
    "            k=k2\n",
    "            while k<m and c[y][k][0]==c[y][k2][0]:\n",
    "                v,nx,ny=c[y][k]\n",
    "                ans=max(ans,dfs(nx,ny)+1)\n",
    "                k+=1\n",
    "            return ans\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans=max(ans,dfs(i,j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIncreasingCells(self, a: List[List[int]]) -> int:\n",
    "        m, n = len(a), len(a[0])\n",
    "        g = defaultdict(list)\n",
    "        ind = defaultdict(int)\n",
    "        # self.ans = -1 \n",
    "        def f(x, ix) :#i,j  ix \n",
    "            nonlocal g \n",
    "            nonlocal ind \n",
    "            t = defaultdict(list)\n",
    "            for i, j, k in x:\n",
    "                t[k].append((i, j))\n",
    "            s = sorted(set(t.keys())) \n",
    "            if len(s)>1:\n",
    "                for j in range(1, len(s)):\n",
    "                    tmp = list(ix)\n",
    "                    tmp.append(s[j])\n",
    "                    tmp = tuple(tmp)\n",
    "                    for i in t[s[j-1]]:\n",
    "                        # g[i].append(ix)\n",
    "                        # tmp = list(ix)\n",
    "                        # tmp.append(s[j]) \n",
    "                        # tmp = tuple(tmp)\n",
    "                        g[i].append(tmp)\n",
    "                        ind[tmp] += 1 \n",
    "                    for i in t[s[j]]:\n",
    "                        # tmp = list(ix)\n",
    "                        # tmp.append(s[j])\n",
    "                        # tmp = tuple(tmp)\n",
    "                        g[tmp].append(i) \n",
    "                        # tmp = list(ix)\n",
    "\n",
    "                        ind[i] += 1\n",
    "                    \n",
    "\n",
    "        for i in range(m):\n",
    "            t = [(i, j, a[i][j]) for j in range(n)]\n",
    "            f(t, (-1, i)) \n",
    "        for j in range(n):\n",
    "            t = [(i, j, a[i][j]) for i in range(m)]\n",
    "            f(t, (-2, j)) \n",
    "        v = defaultdict(int)\n",
    "        def dfs(x):\n",
    "            if x[0]>=0:\n",
    "                v[x] += 1 \n",
    "            for j in g[x]:\n",
    "                ind[j] -= 1  \n",
    "                v[j] = max(v[j], v[x])\n",
    "                if ind[j]==0:\n",
    "                    dfs(j) \n",
    "        ans = [(i, j) for i in range(m) for j in range(n) if not ind[(i, j)]]\n",
    "        # for i in range(m):\n",
    "            # for j in range(n):\n",
    "                # if ind[(i, j)]==0:\n",
    "                    # ans.append([i, j])\n",
    "                    # print(i, j)\n",
    "                    # dfs((i, j))\n",
    "        for i, j in ans:\n",
    "            dfs((i, j))\n",
    "        # print(g)\n",
    "        return max(v.values())\n",
    "        # defaultdict(<class 'list'>, {(0, 1): [(-1, 0), (-2, 1)], (-1, 0): [(0, 0)], (1, 0): [(-1, 1)], (-1, 1): [(1, 1)], (-2, 1): [(1, 1)], (0, 0): [], (1, 1): []})\n",
    "                    \n",
    "  \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
